package a00_LeetCode.Tree;

/**
 * @Author quan
 * @Description  构造最大二叉树
 * @Date 2023/4/2 17:40
 */
public class Num654_contructMaxTree {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        //数组：[3,2,1,6,0,5]
        //找出数组中的最大值:root = 6
        //递归的构造左树：区间范围[3,2,1]
        //递归的构造右树：区间范围[0,5]
      return build(nums,0,nums.length-1);
    }
    public TreeNode build(int[] arr,int left,int right){
        //base case
        if(left > right){
            return null;
        }
        //找到数组中的最大值和对应的索引
        int maxIndex = 0, maxValue = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > maxValue){
                maxIndex = i;
                maxValue = arr[i];
            }
        }
        //先构造出根节点
        TreeNode root = new TreeNode(maxValue);
        //递归调用来构造左右子树
        root.left = build(arr,left,maxIndex-1);
        root.right = build(arr,maxIndex+1,right);
        return root;
    }
}
